package algorithm.beforestart.primary.linkList;

import java.util.Stack;

public class isPalindrome {

    public static boolean isPalindrome(ListNode head) {

        int length =getlentth(head);
        if(length==1){
            return true;
        }

        int n =length/2;
        int flag =length%2;

        Stack<ListNode> stack =new Stack<>();
        ListNode node =head;
        for(int i=1;i<=n;i++){
            stack.push(node);
            node =node.next;
        }

        if (flag==1){
            node=node.next;
        }

        for(int j =1;j<=n;j++){
            if(node.val!=stack.pop().val){
                return false;
            }
            node=node.next;
        }

        return true;


    }


    public static int getlentth(ListNode head){
        if(head==null){
            return 0;
        }
        if(head.next==null){
            return 1;
        }
        return 1+getlentth(head.next);
    }
    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(1);
//        node.next.next.next = new ListNode(1);

        System.out.println(isPalindrome(node));


    }



}
